package 题目集.链表;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
//https://pintia.cn/problem-sets/1734589674052866048/exam/problems/1734589708576198658?type=7&page=0
public class 重排链表 {
    public static void main(String[] args) throws IOException {
//        Map<Integer, Node> map = new HashMap<>();
        Node[] map=new Node[1000_00];
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String[] read = null;
        read = in.readLine().split(" ");
        int head1 = Integer.parseInt(read[0]);
        int n = Integer.parseInt(read[1]);
        for (int i = 0; i < n; i++) {
            read = in.readLine().split(" ");
            int addr = Integer.parseInt(read[0]);
            int val = Integer.parseInt(read[1]);
            int next = Integer.parseInt(read[2]);
            map[addr]=new Node(addr, val, next);
        }
        int curr = head1;
        List<Node> list=new ArrayList<>();
        while (curr!=-1){
            Node node =map[curr];
            list.add(node);
            curr = node.nextAddr;
        }
        int l=0,r=list.size()-1;
        boolean flag=true;
        while (l<=r){
            if (flag){
                Node right = list.get(r);
                Node lefht = list.get(l);
                right.next=lefht;
                right.nextAddr= lefht.addr;
                r--;
            }else {
                Node lefht = list.get(l);
                Node right = list.get(r);
                lefht.next=right;
                lefht.nextAddr= right.addr;
                l++;
            }
            flag=!flag;
        }
        Node last = list.get((list.size()-1)/2);
        last.next=null;
        last.nextAddr=-1;
        print(list.get(list.size()-1));
    }
    public static void print(Node head){
        while (head != null) {
            System.out.println(head);
            head=head.next;
        }
    }

    /**
     * 返回新的头节点
     */
    public static Node reversal(Node head) {
        if (head == null || head.next == null) {
            return head;
        }
        Node newHead = reversal(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }

    static class Node {
        int addr;
        int val;
        int nextAddr;
        Node next;

        public Node(int addr, int val, int nextAddr) {
            this.addr = addr;
            this.val = val;
            this.nextAddr = nextAddr;
        }

        @Override
        public String toString() {
            StringBuilder sb=new StringBuilder();
            sb.append(String.format("%05d", addr)).append(" ").append(val).append(" ");
            if (nextAddr==-1){
                sb.append(-1);
            }else {
                sb.append(String.format("%05d", nextAddr));
            }
            return sb.toString();
        }
    }
}

